<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>leetcode &amp; 蓝桥 | Hexo</title>
  <meta name="keywords" content="">
  <meta name="description" content="leetcode &amp; 蓝桥 | Hexo">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="第二章 线性表线性表：表内数据类型相同，有限序列 本章将以总结的形式展现： 2.1 顺序表与链式表的区别     顺序表 链式表     存取 随机存取 顺序存取   结构 顺序存储（连续） 随机存储（不连续）   空间分配 静态存储（可以动态分配） 动态存储   操作 查找 O(1) ,插入和删除O（n） 查找 O(n) ,插入和删除O（1）   缺点 插入删除不便，长度不可以改变 查找速度慢，">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构">
<meta property="og:url" content="http://yoursite.com/2021/03/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="第二章 线性表线性表：表内数据类型相同，有限序列 本章将以总结的形式展现： 2.1 顺序表与链式表的区别     顺序表 链式表     存取 随机存取 顺序存取   结构 顺序存储（连续） 随机存储（不连续）   空间分配 静态存储（可以动态分配） 动态存储   操作 查找 O(1) ,插入和删除O（n） 查找 O(n) ,插入和删除O（1）   缺点 插入删除不便，长度不可以改变 查找速度慢，">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171951-630686.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171844-136893.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/203103-111988.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171839-101678.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/200119-510473.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202103/05/113954-515448.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/203146-263519.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153239-688589.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153248-836462.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153259-101399.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202103/11/113055-306258.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/151817-474283.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/02/103950-168345.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/02/105245-140913.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153313-134836.png">
<meta property="article:published_time" content="2021-03-11T16:00:00.000Z">
<meta property="article:modified_time" content="2021-03-11T07:19:09.038Z">
<meta property="article:author" content="MOLU">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171951-630686.png">


<link rel="icon" href="/img/avatar.jpg">

<link href="/css/style.css?v=1.1.0" rel="stylesheet">

<link href="/css/hl_theme/github.css?v=1.1.0" rel="stylesheet">

<link href="//cdn.jsdelivr.net/npm/animate.css@4.1.0/animate.min.css" rel="stylesheet">

<script src="//cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js"></script>
<script src="/js/titleTip.js?v=1.1.0" ></script>

<script src="//cdn.jsdelivr.net/npm/highlightjs@9.16.2/highlight.pack.min.js"></script>
<script>
    hljs.initHighlightingOnLoad();
</script>

<script src="//cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.js"></script>



<script src="//cdn.jsdelivr.net/npm/jquery.cookie@1.4.1/jquery.cookie.min.js" ></script>

<script src="/js/iconfont.js?v=1.1.0" ></script>

<meta name="generator" content="Hexo 5.0.0"></head>
<div style="display: none">
  <input class="theme_disqus_on" value="false">
  <input class="theme_preload_comment" value="">
  <input class="theme_blog_path" value="">
  <input id="theme_shortcut" value="true" />
</div>


<body>
<aside class="nav">
    <div class="nav-left">
        <a href="/" class="avatar_target">
    <img class="avatar" src="/img/avatar.jpg" />
</a>
<div class="author">
    <span>MOLU</span>
</div>

<div class="icon">
    
        
        <a title="rss" href="/atom.xml" target="_blank">
            
                <i class="iconfont icon-rss"></i>
            
        </a>
        
    
        
        <a title="github" href="https://github.com/molu-ggg" target="_blank">
            
                <i class="iconfont icon-github"></i>
            
        </a>
        
    
        
    
        
    
        
        <a title="email" href="mailto:2572876783@qq.com" target="_blank">
            
                <i class="iconfont icon-email"></i>
            
        </a>
        
    
</div>




<ul>
    <li><div class="all active" data-rel="All">All<small>(35)</small></div></li>
    
        
            
            <li><div data-rel="AI论文">AI论文<small>(5)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="专业知识">专业知识<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="数学">数学<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="机器学习">机器学习<small>(12)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="经典算法">经典算法<small>(10)</small></div>
                
            </li>
            
        
    
</ul>
<div class="left-bottom">
    <div class="menus">
    
    
    
    
    </div>
    <div><a class="about  hasFriend  site_url"  href="/about">About</a><a style="width: 50%"  class="friends">Friends</a></div>
</div>
<input type="hidden" id="yelog_site_posts_number" value="35">

<div style="display: none">
    <span id="busuanzi_value_site_uv"></span>
    <span id="busuanzi_value_site_pv"></span>
</div>

    </div>
    <div class="nav-right">
        <div class="friends-area">
    <div class="friends-title">
        Links
        <i class="iconfont icon-left"></i>
    </div>
    <div class="friends-content">
        <ul>
            
            <li><a target="_blank" href="http://yelog.org/">叶落阁</a></li>
            
        </ul>
    </div>
</div>
        <div class="title-list">
    <div class="right-top">
        <div id="default-panel">
            <i class="iconfont icon-search" data-title="搜索 快捷键 i"></i>
            <div class="right-title">All</div>
            <i class="iconfont icon-file-tree" data-title="切换到大纲视图 快捷键 w"></i>
        </div>
        <div id="search-panel">
            <i class="iconfont icon-left" data-title="返回"></i>
            <input id="local-search-input" />
            <label class="border-line" for="input"></label>
            <i class="iconfont icon-case-sensitive" data-title="大小写敏感"></i>
            <i class="iconfont icon-tag" data-title="标签"></i>
        </div>
        <div id="outline-panel" style="display: none">
            <div class="right-title">大纲</div>
            <i class="iconfont icon-list" data-title="切换到文章列表"></i>
        </div>
    </div>

    <div class="tags-list">
    <input id="tag-search" />
    <div class="tag-wrapper">
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>50</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>AI</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>数据结构，最短路径，图</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>机器学习</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>相似度计算</a>
            </li>
        
    </div>

</div>

    
    <div id="local-search-result">

    </div>
    
    <nav id="title-list-nav">
        
        <a id="top" class="All 经典算法 "
           href="/2020/07/20/b_leetcode/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="leetcode &amp; 蓝桥">leetcode &amp; 蓝桥</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a id="top" class="All AI论文 "
           href="/2020/07/10/d_GAT/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GAT">GAT</span>
            <span class="post-date" title="2020-07-10 08:50:20">2020/07/10</span>
        </a>
        
        <a  class="All 专业知识 "
           href="/2021/03/12/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="计算机组成原理">计算机组成原理</span>
            <span class="post-date" title="2021-03-12 00:00:00">2021/03/12</span>
        </a>
        
        <a  class="All 专业知识 "
           href="/2021/03/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="数据结构">数据结构</span>
            <span class="post-date" title="2021-03-12 00:00:00">2021/03/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/12/05/b_%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E4%B8%8E%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="动态规划记忆化">动态规划记忆化</span>
            <span class="post-date" title="2020-12-05 00:00:00">2020/12/05</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/07/25/d_300-paperDAT/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="DAT for recommender">DAT for recommender</span>
            <span class="post-date" title="2020-07-25 08:50:20">2020/07/25</span>
        </a>
        
        <a  class="All 数学 "
           href="/2020/07/20/a_%E7%AE%97%E6%B3%95/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="算法总结">算法总结</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a  class="All 数学 "
           href="/2020/07/20/a_%E6%95%B0%E5%AD%A6/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="数学">数学</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a  class="All "
           href="/2020/07/05/%E5%AF%B9%E9%9A%90%E7%A7%98%E7%9A%84%E8%A7%92%E8%90%BD%E7%94%B5%E8%A7%86%E5%89%A7%E7%9A%84%E6%84%9F%E6%82%9F%E4%BB%A5%E5%8F%8A%E8%AE%A4%E8%AF%86/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="对隐秘的角落电视剧的感悟以及认识">对隐秘的角落电视剧的感悟以及认识</span>
            <span class="post-date" title="2020-07-05 00:00:00">2020/07/05</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/07/04/a_%E6%A8%A1%E6%9D%BF%E5%BA%93/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="模板库">模板库</span>
            <span class="post-date" title="2020-07-04 08:50:20">2020/07/04</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/07/04/a_%E7%99%BE%E5%BA%A6%E6%8A%80%E6%9C%AF%E8%AE%A4%E8%AF%81/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="百度技术认证">百度技术认证</span>
            <span class="post-date" title="2020-07-04 08:50:20">2020/07/04</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/07/01/d_GCN%E8%AE%BA%E6%96%87%E8%A7%A3%E8%AF%BB/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GCN">GCN</span>
            <span class="post-date" title="2020-07-01 08:50:20">2020/07/01</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/06/04/d_word2vec_node2vec/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="Word2vec &amp; Node2vec">Word2vec &amp; Node2vec</span>
            <span class="post-date" title="2020-06-04 08:50:20">2020/06/04</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/05/05/d_GAN/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GAN">GAN</span>
            <span class="post-date" title="2020-05-05 08:50:20">2020/05/05</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/05/04/d_Deepwalk/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="DEEPWALK">DEEPWALK</span>
            <span class="post-date" title="2020-05-04 08:50:20">2020/05/04</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/15/b_%E8%B4%AA%E5%BF%83/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="贪心与动态规划">贪心与动态规划</span>
            <span class="post-date" title="2020-02-15 00:00:00">2020/02/15</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/02/12/a_2020/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="机器学习零散知识记录">机器学习零散知识记录</span>
            <span class="post-date" title="2020-02-12 00:00:00">2020/02/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/12/b_%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="动态规划——背包问题">动态规划——背包问题</span>
            <span class="post-date" title="2020-02-12 00:00:00">2020/02/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/03/b_%E8%93%9D%E6%A1%A5%E6%9D%AF%E7%BB%83%E4%B9%A0%E9%A2%98/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="蓝桥杯">蓝桥杯</span>
            <span class="post-date" title="2020-02-03 00:00:00">2020/02/03</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/01/20/c_%E5%86%B3%E7%AD%96%E6%A0%91/"
           data-tag="50"
           data-author="" >
            <span class="post-title" title="决策树总结">决策树总结</span>
            <span class="post-date" title="2020-01-20 00:00:00">2020/01/20</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/01/12/b_%E5%85%A8%E6%8E%92%E5%88%97/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="全排列">全排列</span>
            <span class="post-date" title="2020-01-12 00:00:00">2020/01/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/12/02/b_%E6%9C%89%E7%A9%B7%E8%87%AA%E5%8A%A8%E6%9C%BA/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="有穷自动机">有穷自动机</span>
            <span class="post-date" title="2019-12-02 00:00:00">2019/12/02</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/11/20/b_%E9%94%99%E6%8E%92%E5%85%AC%E5%BC%8F/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="错排公式">错排公式</span>
            <span class="post-date" title="2019-11-20 00:00:00">2019/11/20</span>
        </a>
        
        <a  class="All "
           href="/2019/10/29/a_%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7/"
           data-tag="数据结构，最短路径，图"
           data-author="" >
            <span class="post-title" title="最短路径之弗洛伊德算法">最短路径之弗洛伊德算法</span>
            <span class="post-date" title="2019-10-29 00:00:00">2019/10/29</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/08/04/c_BPR/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="贝叶斯">贝叶斯</span>
            <span class="post-date" title="2019-08-04 08:50:20">2019/08/04</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/08/02/c_matrix/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="矩阵分解与正则化">矩阵分解与正则化</span>
            <span class="post-date" title="2019-08-02 08:25:59">2019/08/02</span>
        </a>
        
        <a  class="All "
           href="/2019/07/28/c_coordination1/"
           data-tag="AI,机器学习,相似度计算"
           data-author="" >
            <span class="post-title" title="协同过滤-上">协同过滤-上</span>
            <span class="post-date" title="2019-07-28 08:25:59">2019/07/28</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/26/c_cnn/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="cnn">cnn</span>
            <span class="post-date" title="2019-07-26 18:54:51">2019/07/26</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/22/c_coordination2/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="协同过滤—下">协同过滤—下</span>
            <span class="post-date" title="2019-07-22 18:54:26">2019/07/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/22/c_kmeans/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="K-means算法">K-means算法</span>
            <span class="post-date" title="2019-07-22 18:53:07">2019/07/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/21/c_nerve2/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="神经网络-下">神经网络-下</span>
            <span class="post-date" title="2019-07-21 11:37:18">2019/07/21</span>
        </a>
        
        <a  class="All "
           href="/2019/07/20/c_nerve1/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="神经网络—上">神经网络—上</span>
            <span class="post-date" title="2019-07-20 17:29:10">2019/07/20</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/06/22/c_gradient/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="线性回归与梯度下降算法">线性回归与梯度下降算法</span>
            <span class="post-date" title="2019-06-22 08:26:36">2019/06/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/06/19/c_flyback/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="线性回归">线性回归</span>
            <span class="post-date" title="2019-06-19 00:00:00">2019/06/19</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/05/20/b_%E8%A7%86%E9%A2%91%E7%BB%8F%E5%85%B8%E7%AE%97%E6%B3%95/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="简单入门算法">简单入门算法</span>
            <span class="post-date" title="2019-05-20 00:00:00">2019/05/20</span>
        </a>
        
        <div id="no-item-tips">

        </div>
    </nav>
    <div id="outline-list">
    </div>
</div>
    </div>
    <div class="hide-list">
        <div class="semicircle" data-title="切换全屏 快捷键 s">
            <div class="brackets first"><</div>
            <div class="brackets">&gt;</div>
        </div>
    </div>
</aside>
<div id="post">
    <div class="pjax">
        <article id="post-b_leetcode" class="article article-type-post" itemscope itemprop="blogPost">
    
        <h1 class="article-title">leetcode &amp; 蓝桥</h1>
    
    <div class="article-meta">
        
        <span class="top"><a>置顶</a></span>
        
        
        
        <span class="book">
            <i class="iconfont icon-category"></i>
            
            
            <a  data-rel="经典算法">经典算法</a>
            
        </span>
        
        
    </div>
    <div class="article-meta">
        
            Created At : <time class="date" title='Updated At: 2020-09-03 20:16:07'>2020-07-20 00:00</time>
        
    </div>
    <div class="article-meta">
        
        
        <span id="busuanzi_container_page_pv">
            Views 👀 :<span id="busuanzi_value_page_pv">
                <span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </span>
        </span>
        
        
    </div>
    
    <div class="toc-ref">
    
        <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%93%88%E5%B8%8C%E8%A1%A8%EF%BC%9A"><span class="toc-text">哈希表：</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#714%E5%8F%8C%E6%8C%87%E9%92%88%E6%B3%95%EF%BC%9A"><span class="toc-text">714双指针法：</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#z%E5%BD%A2%E7%8A%B6%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="toc-text">z形状字符串</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#716"><span class="toc-text">716</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#785-%E5%88%A4%E6%96%AD%E4%BA%8C%E5%88%86%E5%9B%BE"><span class="toc-text">785. 判断二分图</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%95%B4%E6%95%B0%E8%BD%AC%E7%BD%97%E9%A9%AC%E6%95%B0%E5%AD%97"><span class="toc-text">整数转罗马数字</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C-%E5%8F%8C%E6%8C%87%E9%92%88"><span class="toc-text">三数之和-双指针</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#718"><span class="toc-text">718</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#33-%E6%90%9C%E7%B4%A2%E6%97%8B%E8%BD%AC%E6%8E%92%E5%BA%8F%E6%95%B0%E7%BB%84"><span class="toc-text">33. 搜索旋转排序数组</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#97-%E4%BA%A4%E9%94%99%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="toc-text">97. 交错字符串</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#720"><span class="toc-text">720</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#95-%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91-II"><span class="toc-text">95. 不同的二叉搜索树 II</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#62-%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84"><span class="toc-text">62. 不同路径</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#722"><span class="toc-text">722</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#154-%E5%AF%BB%E6%89%BE%E6%97%8B%E8%BD%AC%E6%8E%92%E5%BA%8F%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E6%9C%80%E5%B0%8F%E5%80%BC-II"><span class="toc-text">154. 寻找旋转排序数组中的最小值 II</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#10-%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%8C%B9%E9%85%8D"><span class="toc-text">10. 正则表达式匹配</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#724"><span class="toc-text">724</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#1025-%E9%99%A4%E6%95%B0%E5%8D%9A%E5%BC%88"><span class="toc-text">1025. 除数博弈</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#726"><span class="toc-text">726</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#801-%E5%85%B3%E9%94%AE%E8%B7%AF%E5%BE%84"><span class="toc-text">801 关键路径</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#802"><span class="toc-text">802</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%B0%8F%E6%9C%8B%E5%8F%8B%E6%8E%92%E9%98%9F%EF%BC%9A"><span class="toc-text">小朋友排队：</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9C%B0%E5%AE%AB%E5%8F%96%E5%AE%9D"><span class="toc-text">地宫取宝</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#804"><span class="toc-text">804</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#806"><span class="toc-text">806</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%BF%9E%E9%94%81%E5%8F%8D%E5%BA%94-%E5%A4%A7%E6%95%B0%E7%9B%B8%E4%B9%98"><span class="toc-text">连锁反应 + 大数相乘</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9C%BA%E7%BB%84%E2%80%94TOY%E8%AE%A1%E7%AE%97%E6%9C%BA%E5%BB%BA%E6%A8%A1%E4%B8%8E%E6%A8%A1%E6%8B%9F"><span class="toc-text">机组—TOY计算机建模与模拟</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#810"><span class="toc-text">810</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#811"><span class="toc-text">811</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#1540-%E6%A3%8B%E7%9B%98%E5%A4%9A%E9%A1%B9%E5%BC%8F"><span class="toc-text">1540: 棋盘多项式</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#812"><span class="toc-text">812</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#813"><span class="toc-text">813</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%82%AE%E7%A5%A8%E9%9D%A2%E5%80%BC%E8%AE%BE%E8%AE%A1"><span class="toc-text">邮票面值设计</span></a></li></ol></li></ol>
    
<style>
    .left-col .switch-btn,
    .left-col .switch-area {
        display: none;
    }
    .toc-level-4 i,
    .toc-level-4 ol {
        display: none !important;
    }
</style>
</div>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>快乐数</p>
<p>简单题，但是复杂度的分析是个难题</p>
<p>同时，学会 <code>getNext</code> ，快慢指针方法，哈希表</p>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/">https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/</a></p>
<h1 id="哈希表："><a href="#哈希表：" class="headerlink" title="哈希表："></a>哈希表：</h1><p>有好多种哈希表，需要仔细的研究一下，如何构建哈希表</p>
<p>哈希表有：平方取中法，折叠法，除数余数法</p>
<p>构造一个映射函数，是关键所在。</p>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/">https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/</a></p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202007/11/173757-758490.jpeg" alt="img"></p>
<h1 id="714双指针法："><a href="#714双指针法：" class="headerlink" title="714双指针法："></a>714双指针法：</h1><p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/container-with-most-water/">https://leetcode-cn.com/problems/container-with-most-water/</a></p>
<p>该体暴力法修剪能够运行，</p>
<p>技巧法：双指针法。</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202008/13/204745-238679.png" alt="image-20200714185241352"></p>
<p>题目特点：双变量，长和宽都在变化，求最值问题</p>
<p>我们知道：两个边隔着越远，越高则越大</p>
<p>隔着越远，我们可以操作，那就是从两端开始比较</p>
<p>下一步就是把不可能比当前解还优的情况去掉：</p>
<p>以图中的例子，我们发现：以左1为边的情况，与中间灰色柱子为右边所围成的长方形不可能比当前状态优秀，因此可以不考虑。则直接跳转 左边为第二个柱子的情况</p>
<p>同理，根据对称性，如果当前最左边比最右边高，则以最右边为边的最优值就是当前值</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202008/13/211203-171262.jpeg" alt="img"></p>
<p>枚举方法中省时间的办法，从双向移动，从而演变<strong>为双指针法</strong></p>
<p>算法：就是从两端开始，谁矮谁向里面移动</p>
<p>证明：</p>
<p>若最开始如图，左1&lt;右1，则以左1为一条边的所有正方形都不如当前的大，所以换下一条左边</p>
<p>若左n&gt;右m，则应该以右m为正方形的最右边一定没有当前的大，（包括在n~m之间的，n之前的在前面的左i,i&lt;n为左边的时候就已经不可能成为最大值。</p>
<p>以此类推一直到n&gt;=m结束</p>
<pre><code class="lang-c++">class Solution &amp;#123;
public:
    int maxArea(vector&lt;int&gt;&amp; height) &amp;#123;
        int l = 0, r = height.size() - 1;
        int ans = 0;
        while (l &lt; r) &amp;#123;
            int area = min(height[l], height[r]) * (r - l);
            ans = max(ans, area);
            if (height[l] &lt;= height[r]) &amp;#123;
                ++l;
            &amp;#125;
            else &amp;#123;
                --r;
            &amp;#125;
        &amp;#125;
        return ans;
    &amp;#125;
&amp;#125;;
</code></pre>
<h2 id="z形状字符串"><a href="#z形状字符串" class="headerlink" title="z形状字符串"></a>z形状字符串</h2><p>启示：</p>
<p>o(n)算法；化时间为空间</p>
<p>边走边存，变量碰边改变方向（递增还是递减</p>
<h1 id="716"><a href="#716" class="headerlink" title="716"></a>716</h1><p>:100: <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/is-graph-bipartite/">https://leetcode-cn.com/problems/is-graph-bipartite/</a></p>
<h2 id="785-判断二分图"><a href="#785-判断二分图" class="headerlink" title="785. 判断二分图"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/is-graph-bipartite/">785. 判断二分图</a></h2><p>难度中等163收藏分享切换为英文关注反馈</p>
<p>给定一个无向图<code>graph</code>，当这个图为二分图时返回<code>true</code>。</p>
<p>如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。</p>
<p><code>graph</code>将会以邻接表方式给出，<code>graph[i]</code>表示图中与节点<code>i</code>相连的所有节点。每个节点都是一个在<code>0</code>到<code>graph.length-1</code>之间的整数。这图中没有自环和平行边： <code>graph[i]</code> 中不存在<code>i</code>，并且<code>graph[i]</code>中没有重复的值</p>
<p>一条边的两端肯定是在两个子集中，染不同的颜色，染0/1两种颜色，谁0谁1 就要看是否有与两个端点的染色情况。</p>
<p>若出现一条边两个端点有颜色且颜色相同，则失败。</p>
<p>若出现只有一个点染色，则把另一条边染相反的颜色。</p>
<p>再者，这是一个图，图的遍历有两种，dfs与bfs，这里采用bfs</p>
<p>:a: 这里要区别图的遍历与数组的遍历方法</p>
<pre><code class="lang-c++">class Solution &amp;#123;
public:
    bool isBipartite(vector&lt;vector&lt;int&gt;&gt;&amp; graph) &amp;#123;
      int vis[99999],k=0;
      queue&lt;int&gt;q;
      for (int i=0;i&lt;graph.size();i++)&amp;#123;
            if(graph[i].size()&gt;0) &amp;#123;
                k=i;break;
            &amp;#125;
      &amp;#125;
      q.push(k);
      vis[k]=1;
      while(!q.empty())&amp;#123;
          k = q.front();
          q.pop();

         for(int i=0;i&lt;=graph[k].size();i++)&amp;#123;
             int m = graph[k][i];
             if(vis[m]==0) vis[m]=-vis[k],q.push(m);
             else &amp;#123;
                 if(vis[m]==vis[k]) return 0;
                 else continue;
             &amp;#125;
         &amp;#125;

      &amp;#125;
       return 1;

    &amp;#125;
&amp;#125;;
</code></pre>
<h2 id="整数转罗马数字"><a href="#整数转罗马数字" class="headerlink" title="整数转罗马数字"></a>整数转罗马数字</h2><p>数字中的贪心问题：</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202007/16/171510-803032.png" alt="在这里插入图片描述"></p>
<p>可以这样做，当前数num，</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202007/16/171545-423563.jpeg" alt="img"></p>
<p>每一次从小到大的与上述数组比较即可。</p>
<h2 id="三数之和-双指针"><a href="#三数之和-双指针" class="headerlink" title="三数之和-双指针"></a>三数之和-双指针</h2><p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/3sum/">https://leetcode-cn.com/problems/3sum/</a></p>
<p>排序sort，不重复枚举；</p>
<p>三重循环，第二层和第三层实际上是并列关系，大小的排序已经固定</p>
<p>第一层枚举a</p>
<p>第二层，第三层用一个双指针法o(n)空间的大小</p>
<p>从左到右枚举b，b增大，由于b+c=-a固定，c一定减小，</p>
<pre><code class="lang-c++">class Solution &amp;#123;
public:
    vector&lt;vector&lt;int&gt;&gt; threeSum(vector&lt;int&gt;&amp; nums) &amp;#123;

       int n =nums.size ();
       vector&lt;vector&lt;int&gt;&gt; ans;
       int pai[4];
       int times=0;

       sort(nums.begin(),nums.end());

       for(int i=0;i&lt;nums.size();i++)&amp;#123;
           if(i&gt;0&amp;&amp;nums[i]==nums[i-1]) continue ;
          int j=i+1;
          int c=nums.size()-1;
          while(j&lt;c)&amp;#123;
              if(j&gt;i+1&amp;&amp;nums[j]==nums[j-1]) &amp;#123;j++;continue;&amp;#125;
              if(c&lt;nums.size()-1&amp;&amp;nums[c]==nums[c+1]) &amp;#123;c--;continue;&amp;#125;

              if(-nums[i]&gt;nums[j]+nums[c]) j++;
              else if (-nums[i]&lt;nums[j]+nums[c]) c--;
              else &amp;#123;
                  ans.push_back(&amp;#123;nums[i],nums[j],nums[c]&amp;#125;);
                  j++;
              &amp;#125;
          &amp;#125;
       &amp;#125;
       return ans;

    &amp;#125;
&amp;#125;;
</code></pre>
<h1 id="718"><a href="#718" class="headerlink" title="718"></a>718</h1><h2 id="33-搜索旋转排序数组"><a href="#33-搜索旋转排序数组" class="headerlink" title="33. 搜索旋转排序数组"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/search-in-rotated-sorted-array/">33. 搜索旋转排序数组</a></h2><p>假设按照升序排序的数组在预先未知的某个点上进行了旋转。</p>
<p>( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。</p>
<p>搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。</p>
<p>你可以假设数组中不存在重复的元素。</p>
<p>你的算法时间复杂度必须是 O(log n) 级别。</p>
<p>思路很简单，就是，找到那个轴点，然后分成两个上升数组，就可以了。</p>
<p>思路：</p>
<p>如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [\textit{nums}[l],\textit{nums}[mid])[nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。<br>如果 [mid, r] 是有序数组，且 target 的大小满足 (\textit{nums}[mid+1],\textit{nums}[r]](nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。</p>
<p><img src="E:\typora图片\33_fig1.png" alt="fig1"></p>
<p>下面的代码中有：</p>
<pre><code class="lang-c++">class Solution &amp;#123;
public:
    int search(vector&lt;int&gt;&amp; nums, int target) &amp;#123;
        int n = (int)nums.size();
        if (!n) return -1;
        if (n == 1) return nums[0] == target ? 0 : -1;
        int l = 0, r = n - 1;
        while (l &lt;= r) &amp;#123;
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] &lt;= nums[mid]) &amp;#123;
                if (nums[0] &lt;= target &amp;&amp; target &lt; nums[mid]) &amp;#123;
                    r = mid - 1;
                &amp;#125; else &amp;#123;
                    l = mid + 1;
                &amp;#125;
            &amp;#125; else &amp;#123;
                if (nums[mid] &lt; target &amp;&amp; target &lt;= nums[n - 1]) &amp;#123;
                    l = mid + 1;
                &amp;#125; else &amp;#123;
                    r = mid - 1;
                &amp;#125;
            &amp;#125;
        &amp;#125;
        return -1;
    &amp;#125;
&amp;#125;;
</code></pre>
<p>:a: 也就是说<strong>，对一道题而言，要有一般性，也要考虑特殊性。</strong></p>
<h2 id="97-交错字符串"><a href="#97-交错字符串" class="headerlink" title="97. 交错字符串"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/interleaving-string/">97. 交错字符串</a></h2><p>这道题告诉我们，方法走不通可以巧妙的选择别的方法</p>
<p>:100: 你的动态规划需要继续探索</p>
<h1 id="720"><a href="#720" class="headerlink" title="720"></a>720</h1><h2 id="95-不同的二叉搜索树-II"><a href="#95-不同的二叉搜索树-II" class="headerlink" title="95. 不同的二叉搜索树 II"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/unique-binary-search-trees-ii/">95. 不同的二叉搜索树 II</a></h2><p>:100: 递归构造一棵树，遍历所有节点：</p>
<pre><code class="lang-c++">/**
 * Definition for a binary tree node.
 * struct TreeNode &amp;#123;
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) &amp;#123;&amp;#125;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) &amp;#123;&amp;#125;
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) &amp;#123;&amp;#125;
 * &amp;#125;;
 */
class Solution &amp;#123;
public:
    vector&lt;TreeNode*&gt; generateTrees(int start, int end) &amp;#123;
        if (start &gt; end) &amp;#123;
            return &amp;#123; nullptr &amp;#125;;
        &amp;#125;
        vector&lt;TreeNode*&gt; allTrees;
        // 枚举可行根节点
        for (int i = start; i &lt;= end; i++) &amp;#123;
            // 获得所有可行的左子树集合
            vector&lt;TreeNode*&gt; leftTrees = generateTrees(start, i - 1);

            // 获得所有可行的右子树集合
            vector&lt;TreeNode*&gt; rightTrees = generateTrees(i + 1, end);

            // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
            for (auto&amp; left : leftTrees) &amp;#123;
                for (auto&amp; right : rightTrees) &amp;#123;
                    TreeNode* currTree = new TreeNode(i);
                    currTree-&gt;left = left;
                    currTree-&gt;right = right;
                    allTrees.emplace_back(currTree);
                &amp;#125;
            &amp;#125;
        &amp;#125;
        return allTrees;
    &amp;#125;

    vector&lt;TreeNode*&gt; generateTrees(int n) &amp;#123;
        if (!n) &amp;#123;
            return &amp;#123;&amp;#125;;
        &amp;#125;
        return generateTrees(1, n);
    &amp;#125;
&amp;#125;;
</code></pre>
<h2 id="62-不同路径"><a href="#62-不同路径" class="headerlink" title="62. 不同路径"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/unique-paths/">62. 不同路径</a></h2><p>:100: 排列组合问题</p>
<p>需要看一看</p>
<h1 id="722"><a href="#722" class="headerlink" title="722"></a>722</h1><h2 id="154-寻找旋转排序数组中的最小值-II"><a href="#154-寻找旋转排序数组中的最小值-II" class="headerlink" title="154. 寻找旋转排序数组中的最小值 II"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/">154. 寻找旋转排序数组中的最小值 II</a></h2><p>本题是 153. 寻找旋转排序数组中的最小值 的延伸。读者可以先尝试 153 题，体会在旋转数组中进行二分查找的思路，再来尝试解决本题。</p>
<p>方法一：二分查找<br>思路与算法</p>
<p>一个包含重复元素的升序数组在经过旋转之后，可以得到下面可视化的折线图：</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202007/22/160131-709054.png" alt="fig1"></p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202007/22/160143-61760.png" alt="fig2"></p>
<p>最后一幅图是最不好处理的：</p>
<p>就是当左右两端相等的情况有多种可能：</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202007/22/160151-883430.png" alt="fig4"></p>
<p>这里 处理方法是：high—;</p>
<pre><code class="lang-c++">class Solution &amp;#123;
public:
    int findMin(vector&lt;int&gt;&amp; nums) &amp;#123;
        int low = 0;
        int high = nums.size() - 1;
        while (low &lt; high) &amp;#123;
            int pivot = low + (high - low) / 2;
            if (nums[pivot] &lt; nums[high]) &amp;#123;
                high = pivot;
            &amp;#125;
            else if (nums[pivot] &gt; nums[high]) &amp;#123;
                low = pivot + 1;
            &amp;#125;
            else &amp;#123;
                high -= 1;
            &amp;#125;
        &amp;#125;
        return nums[low];
    &amp;#125;
&amp;#125;;
</code></pre>
<h2 id="10-正则表达式匹配"><a href="#10-正则表达式匹配" class="headerlink" title="10. 正则表达式匹配"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/regular-expression-matching/">10. 正则表达式匹配</a></h2><p>这道题比较难理解，是个字符串的匹配问题，这里用到了动态规划。</p>
<p>首先，对于一般情况，就是不含有，*和.的，可以的转移方程式：</p>
<script type="math/tex; mode=display">
f[i][j]=\left\{\begin{array}{ll}
f[i-1][j-1], & s[i]=p[j] \\
\text { false }, & s[i] \neq p[j]
\end{array}\right.</script><p>现在，考虑这个其次复杂的.,很显然，.存在，一定可以够匹配</p>
<script type="math/tex; mode=display">
\text { f[i][j] }=\left\{\begin{array}{ll}
f[i-1][j-1] \text , & \text { matches }(s[i], p[j]) \\
0, & \text { otherwise }
\end{array}\right.</script><p>matches(s[i],p[j])表示相等，或者p[j]是.</p>
<p>最后，考虑最为复杂的*：</p>
<p>x与*可以与前面的x联合在一起，醉成 x组合，多个*连在一起并没有多大的意义，前期处理可以去掉。</p>
<p>当$s[i]!=p[j-1]$的时候，$f[i][j]=f[i][j-2]$，</p>
<p>当存在一个，$s[i]=p[j-1]$的时候，$f[i][j]=f[i-1][j-2]$</p>
<p>也可以是两个$s[i-1]=s[i]=p[j-1]$，$f[i][j]=f[i-2][j-2]$</p>
<p>也可以是n个,$s[i-n+1]=s[i-n+2]…..=s[i]=p[j-1]$,$f[i][j]=f[i-n][j-2]$</p>
<p>以上可以概括为，</p>
<p>本质上只会有两种情况：</p>
<ul>
<li><p>匹配 <em>s</em> 末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配；</p>
<p>（就是说，s如果存在重复的元素，且与*相遇，则$f[i][j]=f[i-1][j]$)</p>
</li>
<li><p>不匹配字符，将该组合扔掉，不再进行匹配。</p>
</li>
</ul>
<script type="math/tex; mode=display">
f[i][j]=\left\{\begin{array}{ll}
f[i-1][j] \text { or } f[i][j-2], & s[i]=p[j-1] \\
f[i][j-2], & s[i] \neq p[j-1]
\end{array}\right.</script><p>综合上述三个方面，可以列总的状态转移方程为：</p>
<script type="math/tex; mode=display">
f[i][j]=\left\{\begin{array}{l}\text { if }\left(p[j] \neq{ }^{*},\right)=\left\{\begin{array}{ll}f[i-1][j-1], & \text { matches }(s[i], p[j]) \\\text { false, }\end{array}\right. \\\text { otherwise }=\left\{\begin{array}{ll}f[i-1][j] \text { or } f[i][j-2], & \text { otherwise } \\f[i][j-2], & \text { otherwise }\end{array}\right.\end{array}\right.</script><h1 id="724"><a href="#724" class="headerlink" title="724"></a>724</h1><h2 id="1025-除数博弈"><a href="#1025-除数博弈" class="headerlink" title="1025. 除数博弈"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/divisor-game/">1025. 除数博弈</a></h2><p>难度简单203收藏分享切换为英文关注反馈</p>
<p>爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。</p>
<p>最初，黑板上有一个数字 <code>N</code> 。在每个玩家的回合，玩家需要执行以下操作：</p>
<ul>
<li>选出任一 <code>x</code>，满足 <code>0 &lt; x &lt; N</code> 且 <code>N % x == 0</code> 。</li>
<li>用 <code>N - x</code> 替换黑板上的数字 <code>N</code> 。</li>
</ul>
<p>如果玩家无法执行这些操作，就会输掉游戏。</p>
<p>只有在爱丽丝在游戏中取得胜利时才返回 <code>True</code>，否则返回 <code>false</code>。假设两个玩家都以最佳状态参与游戏。</p>
<p>找规律</p>
<p><strong>思路与算法</strong></p>
<p>博弈类的问题常常让我们摸不着头脑。当我们没有解题思路的时候，不妨试着写几项试试：</p>
<p>N = 1的时候，区间 (0, 1)(0,1) 中没有整数是 nn 的因数，所以此时 Alice 败。<br>N = 2的时候，Alice 只能拿 1，N 变成 1，Bob 无法继续操作，故 Alice 胜。<br>N = 3 的时候，Alice 只能拿 1，N 变成 2，根据 N = 2 的结论，我们知道此时 Bob 会获胜，Alice 败。<br>N = 4 的时候，Alice 能拿 1 或 2，如果 Alice 拿 1，根据 NN=3 的结论，Bob 会失败，Alice 会获胜。<br>N = 5的时候，Alice 只能拿 1，根据 N = 4的结论，Alice 会失败。<br>……<br>写到这里，也许你有了一些猜想。没关系，请大胆地猜想，在这种情况下大胆地猜想是 AC 的第一步。也许你会发现这样一个现象：NN 为奇数的时候 Alice（先手）必败，NN 为偶数的时候 Alice 必胜。 这个猜想是否正确呢？下面我们来想办法证明它。</p>
<p><strong>证明</strong></p>
<p>数学归纳：</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202007/24/220830-607827.png" alt="image-20200724220827637"></p>
<h1 id="726"><a href="#726" class="headerlink" title="726"></a>726</h1><pre><code class="lang-c++">
class Solution &amp;#123;
public:
    int dx[5]=&amp;#123;0,0,1,-1&amp;#125;;
    int dy[5]=&amp;#123;1,-1,0,0&amp;#125;;
    int maxn =0 ;
    vector&lt;int&gt; dir[666666];
    vector&lt;int&gt; flag[500000] ;
    void dfs( int x,int size  )&amp;#123;

        if(dir[x].size()==0)&amp;#123;
        int xx = x/size ;
        int yy =x%size ; 
        maxn =max(maxn, flag[xx][yy]);  
            return ;
        &amp;#125;
      for (int i=0;i&lt;dir[x].size();i++)&amp;#123;
          int xx = x/size ;
          int yy =x%size ; 
          int k = dir[x][i];

       if(flag[xx+dx[k]][yy+dy[k]]&lt;flag[xx][yy]+1) &amp;#123;
            flag[xx+dx[k]][yy+dy[k]]=max(flag[xx+dx[k]][yy+dy[k]],flag[xx][yy]+1);   
           dfs(x+dx[k]*size+dy[k],size);
           &amp;#125;
      &amp;#125;

    &amp;#125;
    int longestIncreasingPath(vector&lt;vector&lt;int&gt;&gt;&amp; matrix) &amp;#123;
             vector&lt;int&gt; start;
            int size =matrix[0].size ();
            //存方向
            if(matrix.size()==0) return 0;

            for (int i=0;i&lt;matrix.size();i++)&amp;#123;
                for (int j=0;j&lt;matrix[0].size();j++)&amp;#123;
                    flag[i].push_back(0);
                    int flag1 =0 ;
                    for (int k=0;k&lt;4;k++)&amp;#123; 
                if(i+dx[k]&lt;0||i+dx[k]&gt;=matrix.size()||j+dy[k]&lt;0||j+dy[k]&gt;=matrix[0].size())
                       &amp;#123;flag1++;&amp;#125;
                else if(matrix[i][j]&lt;matrix[i+dx[k]][j+dy[k]]) 
                       &amp;#123;flag1 ++, dir[size*i+j].push_back(k);&amp;#125;

                else if (matrix[i][j]==matrix[i+dx[k]][j+dy[k]])  flag1++;
                    &amp;#125;
                    if(flag1 ==4) &amp;#123;start.push_back(size*i+j);&amp;#125;//二维转一维
                &amp;#125;
            &amp;#125;


           // return maxn;
            for (int i=0;i&lt;start.size ();i++)&amp;#123;
                int x=start[i]/size;
                int y =start[i]%size;

                dfs(start[i],size );
            &amp;#125;
            //解析:这是找到了最大路径
           return maxn+1;

    &amp;#125;
&amp;#125;;
</code></pre>
<h1 id="801-关键路径"><a href="#801-关键路径" class="headerlink" title="801 关键路径"></a>801 关键路径</h1><p><a target="_blank" rel="noopener" href="https://www.dotcpp.com/oj/problem1433.html">https://www.dotcpp.com/oj/problem1433.html</a></p>
<p>问题描述<br>抗日战争时期，冀中平原的地道战曾发挥重要作用。<br>地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。<br>我们来定义一个危险系数DF(x,y)：<br>对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。<br>本题的任务是：已知网络结构，求两站点之间的危险系数</p>
<p>。</p>
<pre><code class="lang-c++">#include&lt;iostream&gt;
#include&lt;vector&gt;
#include&lt;set&gt;
#include&lt;stdlib.h&gt;
#include &lt;algorithm&gt;  
using namespace std ;
int n,m,u,v,k;
vector&lt;int&gt; a[1002];
vector&lt;int&gt;path[30000];
vector&lt;int&gt;du,c;
int vis[20003];
int ans =0 ;
int times[20002];
void dfs(int x,int y )&amp;#123;    
    if(x==y)&amp;#123;

        //path[++ans].assign(du.begin(),du.end());
        for (int i=0;i&lt;du.size();i++)&amp;#123;
            times[du[i]]++;
        &amp;#125;
        ans++;
        return ;
    &amp;#125;
    for(int i=0;i&lt;a[x].size();i++)&amp;#123;
        int k=a[x][i];
        if(!vis[k]) &amp;#123;
            vis[k]=1;
            du.push_back(k);
            dfs(k,y);
            vis[k]=0;
            du.pop_back();
        &amp;#125;
    &amp;#125;    
&amp;#125;    
int main()&amp;#123;
    int p,q;
    cin&gt;&gt;n&gt;&gt;m;
    for(int i=1;i&lt;=m;i++)&amp;#123;
        cin&gt;&gt;p&gt;&gt;q;
        a[p].push_back(q);
        a[q].push_back(p);
    &amp;#125;
    cin&gt;&gt;u&gt;&gt;v;
    vis[u]=1;
    dfs(u,v);
    if(ans==0)&amp;#123;
        cout&lt;&lt;-1;
    &amp;#125;
    int num=0;
    for(int i=1;i&lt;=n;i++)&amp;#123;
        if(times[i]==ans) num++;
    &amp;#125;
    cout&lt;&lt;num;
&amp;#125;
</code></pre>
<h1 id="802"><a href="#802" class="headerlink" title="802"></a>802</h1><h2 id="小朋友排队："><a href="#小朋友排队：" class="headerlink" title="小朋友排队："></a><a target="_blank" rel="noopener" href="https://www.dotcpp.com/oj/problem1439.html">小朋友排队：</a></h2><p>xdl或者树状数组</p>
<p>n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置<strong>相邻</strong>的两个小朋友。</p>
<p>相邻可以考虑xdl</p>
<p><strong>最少的交换次数，</strong>保证交换尽可能的均匀</p>
<h2 id="地宫取宝"><a href="#地宫取宝" class="headerlink" title="地宫取宝"></a><a target="_blank" rel="noopener" href="https://www.dotcpp.com/oj/problem1436.html">地宫取宝</a></h2><p>这道题我们考虑到了用动态规划，实际上动态规划不仅仅是局限在二维数组，也可以用一维，三维甚至四维数组，这就要根据提供的数据的范围，给个极限。</p>
<p>本题有三个数 50 50 13  </p>
<p>50 <em>50 </em>50 *50 四维数组以内均可以,我尝试的是三维数组，但是无法解决</p>
<p>同时，看见要mod 1000000007 ，一定是个大数，可能要用到剪枝以及记忆化搜索。</p>
<p>动态规划法：</p>
<p>$dp[i][j][k][l]$    前i,j 个格，</p>
<p>尝试：k可以表示现在手中的物品个数</p>
<p>另外，题目中还提供了物品价值的数据范围，且很小可以考虑，当前物品价值不大于l</p>
<p> 当前可以拿这个物品:则说明， 前面的价值一定小于 $c[i][j]$，于是转移方程是：</p>
<p>$dp[i][j][k][l] = dp[i-1][j][k-1][c[i][j]]+dp[i][j-1][k-1][c[i][j]]$</p>
<p>当不可以拿或者不想拿的时候：(直接路线继承，不需要改变或者讨论最小价值以及物品的个数)</p>
<p>$dp[i][j][k][l] = dp[i-1][j][k][l]+dp[i][j-1][k][l]$</p>
<pre><code class="lang-c++">#include &lt;iostream&gt;

#define _for(i,a,b) for(int i=a;i&lt;b;i++)

using namespace std;
typedef long long LL;
LL d[51][51][13][13],mod=1000000007;
int a[55][55];
int main() &amp;#123;
    int n,m,K;
    cin&gt;&gt;n&gt;&gt;m&gt;&gt;K;
    _for(i,0,n)_for(j,0,m)cin&gt;&gt;a[i+1][j+1];
    _for(i,1,n+1)_for(j,1,m+1)_for(k,0,K+1)_for(c,0,13)&amp;#123;
        LL na=0,buna=0;
        if(i==1&amp;&amp;j==1)&amp;#123;
            if(!k||(k==1&amp;&amp;c&gt;a[i][j]))d[i][j][k][c]=1;
            continue;
        &amp;#125;
        if(k&amp;&amp;c&gt;a[i][j])na=d[i-1][j][k-1][a[i][j]]+d[i][j-1][k-1][a[i][j]];
        buna=d[i-1][j][k][c]+d[i][j-1][k][c];
        d[i][j][k][c]=na+buna;
        d[i][j][k][c]%=mod;
    &amp;#125;
    cout&lt;&lt;d[n][m][K][12]&lt;&lt;endl;
&amp;#125;
</code></pre>
<p>dfs + 记忆化搜索+  dp</p>
<pre><code class="lang-c++">#include&lt;iostream&gt;
#define N 1000000007 
#include&lt;cstring&gt;
using namespace std;
int n,m,k;
int mapvalue[51][51];
int dp[55][55][15][15];//动态规划路径 
int dfs(int x,int y,int num,int maxv)&amp;#123;
     //判断路径有没走过 
if(dp[x][y][num][maxv+1]!=-1)
   return dp[x][y][num][maxv+1]; //走过就用统计过的路径(“记忆”的部分) 
if(x==n&amp;&amp;y==m)&amp;#123;  //走到了右下角
     //分拿走或者不拿走右下角那个宝藏,都是一种方案 
   if(num==k||(num==k-1&amp;&amp;maxv&lt;mapvalue[x][y]))
   return dp[x][y][num][maxv+1]=1;
   else return dp[x][y][num][maxv+1]=0;// 否则失败
&amp;#125;
//统计路径方案 
long long s=0;
//向下深搜，分取或者不取这个宝物，由宝物价值判断 
if(x+1&lt;=n)&amp;#123;   //向下控制不出界限 
      if(maxv&lt;mapvalue[x][y])
s+=dfs(x+1,y,num+1,mapvalue[x][y]);
s+=dfs(x+1,y,num,maxv);//也可以不取 
&amp;#125;
//向右深搜 分取或者不取这个宝物，由宝物价值判断
if(y+1&lt;=m)&amp;#123; //向下控制不出界 
if(maxv&lt;mapvalue[x][y])
s+=dfs(x,y+1,num+1,mapvalue[x][y]);
s+=dfs(x,y+1,num,maxv);//也可以不取 
  &amp;#125;
   return dp[x][y][num][maxv+1]=s%N;
&amp;#125;
int main()&amp;#123;
int i,j;
cin&gt;&gt;n&gt;&gt;m&gt;&gt;k;
for(i=1;i&lt;=n;i++)
for(j=1;j&lt;=m;j++)&amp;#123;
  cin&gt;&gt;mapvalue[i][j];
&amp;#125;
memset(dp,-1,sizeof(dp)); 
    dfs(1,1,0,-1);
    cout&lt;&lt;dp[1][1][0][0];
return 0; &amp;#125;
</code></pre>
<h1 id="804"><a href="#804" class="headerlink" title="804"></a>804</h1><p>题目 1449: [蓝桥杯][2014年第五届真题]波动数列</p>
<p>时间限制: 1Sec 内存限制: 128MB 提交: 622 解决: 196</p>
<p>题目描述</p>
<p>观察这个数列：<br>1 3 0 2 -1 1 -2 …</p>
<p>这个数列中后一项总是比前一项增加2或者减少3。</p>
<p>栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢？</p>
<p>样例说明<br>这两个数列分别是2 4 1 3和7 4 1 -2。<br>数据规模和约定<br>对于100%的数据，1&lt; =n&lt; =1000，-1,000,000,000&lt; =s&lt; =1,000,000,000，1&lt; =a, b&lt; =1,000,000。</p>
<p>输入</p>
<p>输入的第一行包含四个整数 n s a b，含义如前面说述。 </p>
<p>输出</p>
<p>输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以100000007的余数。 </p>
<pre><code class="lang-c++">long long int n,s,a,b; 
int F [1001002];
int main()&amp;#123;
     cin&gt;&gt;n&gt;&gt;s&gt;&gt;a&gt;&gt;b;
     F[0] =1 ;
     for (int i=1;i&lt;=n-1;i++)&amp;#123;
         for (int j=i*(i+1)/2;j&gt;=i ;j--)&amp;#123;
             F[j] = (F[j] + F[j-i])%100000007;
         //    cout&lt;&lt;i&lt;&lt;j&lt;&lt;F[j]&lt;&lt;endl;
         &amp;#125;
     &amp;#125;
    long long int sumn = (n)*(n-1)/2 ,ans =0;
   // long long int start_sum = s + (n) * b;

    for (int i=0;i&lt;=sumn ;i++)&amp;#123;
        if((s-i*a+(sumn-i)*b)%n==0) &amp;#123;
        //    cout&lt;&lt; i&lt;&lt; sumn- i&lt;&lt;endl ;
            ans=(ans+F[i])%100000007; 
        &amp;#125;
    &amp;#125;
    cout&lt;&lt;ans ;
    //system(&quot;pause&quot;);

&amp;#125;
</code></pre>
<p>题目 1447: [蓝桥杯][2013年第四届真题]格子刷油漆</p>
<p>时间限制: 1Sec 内存限制: 128MB 提交: 416 解决: 119</p>
<p>题目描述</p>
<p>X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形（如下图所示），现需要把这些格子刷上保护漆。</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202008/04/180416-427184.jpeg" alt="img"><br>你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！）<br>比如：a d b c e f 就是合格的刷漆顺序。<br>c e f d a b 是另一种合适的方案。<br>当已知 N 时，求总的方案数。当N较大时，结果会迅速增大，请把结果对 1000000007 (十亿零七) 取模。</p>
<p>问题分析：</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202008/04/180251-56267.png" alt="img_1110"></p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202008/04/180257-183429.png" alt="img_1111"></p>
<p><img src="E:\typora图片\180306-153877.png" alt="img_1112"></p>
<h1 id="806"><a href="#806" class="headerlink" title="806"></a>806</h1><p>2n皇后</p>
<pre><code class="lang-c++">#include&lt;iostream&gt;
#include &lt;string.h&gt;
#include&lt;bits\stdc++.h&gt;
using namespace std ;
#define MAXN 2003

int line1[MAXN],line2[MAXN],row1[MAXN],row2[MAXN];
int l1[MAXN],l2[MAXN],r1[MAXN],r2[MAXN]; 
int a[MAXN][MAXN];
int n ,ans =0 ;
void dfs(int floor )&amp;#123;
    if(floor == n+1 )&amp;#123;
        ans++;
        return ;
    &amp;#125;

    for (int i =1;i&lt;= n;i++)&amp;#123;
        if(a[floor][i]==1)&amp;#123;
            if(!l1[i+floor]&amp;&amp;!r1[n-i+1+floor]&amp;&amp;!line1[i])&amp;#123;
                for (int j =1;j&lt;=n;j++)&amp;#123;
                    if(i!=j &amp;&amp;a[floor][j]==1)&amp;#123;
                        if(!l2[j+floor]&amp;&amp;!r2[n-j+1+floor]&amp;&amp;!line2[j])&amp;#123;
                            l1[i+floor]=r1[n-i+1+floor]=line1[i]=1;
                            l2[j+floor]=r2[n-j+1+floor]=line2[j]=1;
                            a[floor][i]=a[floor][j]=0;
                            dfs(floor+1);
                            a[floor][i]=a[floor][j]=1;    
                            l1[i+floor]=r1[n-i+1+floor]=line1[i]=0;
                            l2[j+floor]=r2[n-j+1+floor]=line2[j]=0;    
                        &amp;#125;
                    &amp;#125;
                &amp;#125;
            &amp;#125; 
        &amp;#125;
    &amp;#125;
&amp;#125;
int main()&amp;#123;

    cin&gt;&gt; n ;
    for (int i=1;i&lt;=n;i++)&amp;#123;
        for (int j=1;j&lt;=n;j++)&amp;#123;
            cin&gt;&gt;a[i][j];
        &amp;#125;
    &amp;#125;
    dfs(1);
    cout&lt;&lt;ans ;
   // system(&quot;pause&quot;);

&amp;#125;
</code></pre>
<p><a target="_blank" rel="noopener" href="https://www.dotcpp.com/oj/problem1492.html">产生数：</a></p>
<h2 id="连锁反应-大数相乘"><a href="#连锁反应-大数相乘" class="headerlink" title="连锁反应 + 大数相乘"></a>连锁反应 + 大数相乘</h2><p>大数相乘：请你牢牢记住：</p>
<pre><code class="lang-c++">void cheng (int *num ,int k)&amp;#123;
     int copy_num[MAXN];
     memset(copy_num,0,sizeof(copy_num));//一定要初始化 
     int kk = k ;
    for (int i =0 ;i&lt; len ;i++ )&amp;#123;
        kk = k ;
        for (int j = 0 ;kk ; j++)&amp;#123;
            int t = kk%10 ;
            kk/=10;
            copy_num[i+j] += t*num[i];
            if (copy_num[i+j] &amp;&amp; len &lt;= i+ j) len = i+ j+1 ;

        &amp;#125;
    &amp;#125;
    for (int i =0 ;i&lt;len ; i++)&amp;#123;


        copy_num[i+1] += copy_num[i]/10 ; //一定要注意顺序问题 
        copy_num[i] = copy_num[i]%10 ;
        if (copy_num[i+1]&amp;&amp; len &lt;= i+2) len =i+2 ;
    &amp;#125;

    for (int i=0;i&lt;len;i++ )&amp;#123;
        num[i] = copy_num[i];
    &amp;#125;
&amp;#125;
</code></pre>
<pre><code>#include&lt;iostream&gt;
#include &lt;string.h&gt;
//#include&lt;bits\stdc++.h&gt;
using namespace std ;
#define MAXN 2003
int dis[MAXN][MAXN];

int x[MAXN],y[MAXN];
int times[20],flag =0 ;
int num[MAXN],len = 1;
void dfs(int orgin,int j )&amp;#123;
    if( orgin == j)&amp;#123;
        return ;
    &amp;#125;
   flag =1 ;
   for (int k =0;k&lt;=9;k++)&amp;#123;
       if (dis[j][k]==1&amp;&amp; dis[orgin][k]==0&amp;&amp; orgin !=k)&amp;#123;
           dis[orgin][k]=2 ;      
       //    cout &lt;&lt; orgin &lt;&lt; j&lt;&lt; k &lt;&lt;endl;
           times[orgin]++ ;
           dfs(orgin,k);         
       &amp;#125;
   &amp;#125;
&amp;#125;
 void cheng (int *num ,int k)&amp;#123;
     int copy_num[MAXN];
     memset(copy_num,0,sizeof(copy_num));//一定要初始化 
 //    for (int i=len-1 ;i&gt;=0;i--) cout &lt;&lt; num[i];
 //    cout &lt;&lt;&quot; &quot;;
 //    cout &lt;&lt;k&lt;&lt;endl ; 
     int kk = k ;
    for (int i =0 ;i&lt; len ;i++ )&amp;#123;
        kk = k ;
        for (int j = 0 ;kk ; j++)&amp;#123;
            int t = kk%10 ;
            kk/=10;
            copy_num[i+j] += t*num[i];
            if (copy_num[i+j] &amp;&amp; len &lt;= i+ j) len = i+ j+1 ;

        &amp;#125;
    &amp;#125;
    for (int i =0 ;i&lt;len ; i++)&amp;#123;


        copy_num[i+1] += copy_num[i]/10 ; //一定要注意顺序问题 
        copy_num[i] = copy_num[i]%10 ;
        if (copy_num[i+1]&amp;&amp; len &lt;= i+2) len =i+2 ;
    &amp;#125;

    for (int i=0;i&lt;len;i++ )&amp;#123;
        num[i] = copy_num[i];
    &amp;#125;
&amp;#125;
int main()&amp;#123;
    string s ;cin&gt;&gt;s ;
    int k ;
    cin&gt;&gt; k ;
    for (int i=1;i&lt;= k;i++)&amp;#123;
        cin&gt;&gt;x[i]&gt;&gt;y[i];
        dis[x[i]][y[i]]=1;
    &amp;#125;
    for (int i=0;i&lt;=9;i++)&amp;#123;
        for (int j=0;j&lt;=9;j++)&amp;#123;
            if(dis[i][j]==1)&amp;#123;
    //            cout &lt;&lt; i&lt;&lt; j&lt;&lt;endl ;
                times[i]++ ;
                flag = 0 ;
                dfs(i,j) ;
            &amp;#125;

        &amp;#125;
    &amp;#125;
    num[0]= 1 ;
    long long sum =1;
    for(int i=0;i&lt;s.length();i++)&amp;#123;
   //     cout &lt;&lt; times[s[i]-48];
        if(times[s[i]-48]==0) continue ; 
        cheng ( num ,times[s[i]-48]+1);
    //    sum*= ( times[s[i]-48]+1);
    &amp;#125;
    for (int i=len-1;i&gt;=0;i--) cout &lt;&lt; num[i];
    //cout &lt;&lt;endl&lt;&lt;sum;
  // system(&quot;pause&quot;);

&amp;#125;
</code></pre><h2 id="机组—TOY计算机建模与模拟"><a href="#机组—TOY计算机建模与模拟" class="headerlink" title="机组—TOY计算机建模与模拟"></a>机组—TOY计算机建模与模拟</h2><pre><code>mem = [0] * 1000
reg = [0] * 10
pReg = 0
iReg = 0


def printMachineState():
    global pReg, iReg, reg, mem
    print(&#39;       The TOY Machine       &#39;)
    print(&#39;P reg  &#39; + str(pReg) + &#39;       I reg &#39; + str(iReg))
    print(&#39;\n&#39;)
    for i in range(0, 5):
        print(&#39;reg &#39; + str(i) + &#39;  &#39; + str(reg[i]) + &#39;       reg &#39; + str(i + 5) + &#39;  &#39; + str(reg[i + 5]))
    print(&#39;\n&#39;)


def loadProgram(file):
    global pReg, iReg, reg, mem
    fil = open(file, &quot;r&quot;)
    first = True
    while 1:
        lin = fil.readline()
        if lin == &quot;&quot;:
            break
        if lin[0] &lt; &#39;0&#39;:
            continue
        try:
            # 请在此添加代码，补全函数loadProgram
            #-----------Begin----------
            addr = int (lin[:3])

            stru =int ( lin[6:12])
            mem[addr] = stru 
            if first:
                first =False
                pReg = int(addr)


            #------------End-----------
        except:
            pass
    fil.close()


def cycle():
    global pReg, iReg, reg, mem

    # 请在此添加代码，补全函数cycle
    #-----------Begin----------
    #print (pReg)
    iReg = int(mem[pReg]) #从程序寄存器取地址存入指令寄存器
    pReg +=1  #程序寄存器加1
    #译码
    opcode = iReg // 10000 #前两位是操作码
    r = (iReg//1000) %10 #其次一位是寄存器编号
    addr =(iReg)%1000 #后三位是 内存地址，与前面近期编号组合在一起为操作数
    s =addr % 10

    #------------End-----------

    if opcode == 0:
        printMachineState() #打印CPU内部状态信息
        return 0
    elif opcode == 1:
        reg[r] = mem[addr]
    # 请在此添加代码，补全函数cycle
    #-----------Begin----------
    elif opcode == 2:
        mem[addr] = reg[r]
    elif opcode == 3 :
        reg[r] = int( addr )
    elif opcode == 4 : #????
        reg[r] =  mem[reg[s]]
    elif opcode == 5 :
        reg[r] = reg[r] + reg[s]
    elif opcode == 6 :
        reg [r] = reg[r] - reg[s]
    elif opcode == 7 :
        reg [r] = reg[r] * reg[s]
    elif opcode == 8 :
        reg [r] = reg[r] // reg[s] #???
    elif opcode == 10:
         pReg = addr 
    elif opcode == 11 :
        if reg[r] == 0:
            pReg = addr  

    #------------End-----------
    return 1


def run(fileName):
    global pReg, iReg, reg, mem
    printMachineState()
    loadProgram(fileName)
    printMachineState()

    # 请在此添加代码，补全函数run
    #-----------Begin----------
    while 1: 
        k = cycle()
        if k == 0:
            break   
    #------------End-----------


if __name__==&quot;__main__&quot;:
    run(&#39;prog1.mml&#39;)
</code></pre><h1 id="810"><a href="#810" class="headerlink" title="810"></a>810</h1><p>完美的代价</p>
<blockquote>
<p>题目 1467: [蓝桥杯][基础练习VIP]完美的代价</p>
<p>时间限制: 1Sec 内存限制: 128MB 提交: 1269 解决: 497</p>
<p>题目描述</p>
<p>回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。</p>
<p>交换的定义是：交换两个相邻的字符</p>
<p>例如mamad</p>
<p>第一次交换 ad : mamda</p>
<p>第二次交换 md : madma</p>
<p>第三次交换 ma : madam (回文！完美！)</p>
<p>输入</p>
<p>第一行是一个整数N，表示接下来的字符串的长度(N &lt; = 8000) </p>
<p>第二行是一个字符串，长度为N.只包含小写字母 </p>
</blockquote>
<p>解决最优值问题，可以考虑bfs，动态规划，贪心策略等</p>
<p>这里就是用的贪心策略。</p>
<p>先考虑不能的：</p>
<p>① 偶长度，有奇数的个数</p>
<p>②奇数长度，有超过2个字母奇数长度</p>
<p>然后：</p>
<p>从开头开始，遍历，考虑到是对称，应该从后到前进行匹配。</p>
<p>难点就是对于那个奇数点的处理：</p>
<p>学习到的</p>
<pre><code class="lang-c++">s.insert(i,len,s);

s.earse(i,s);
</code></pre>
<p>题目 1478: [蓝桥杯][算法提高VIP]3000米排名预测</p>
<p>时间限制: 1Sec 内存限制: 128MB 提交: 369 解决: 135</p>
<p>题目描述</p>
<p>3000米长跑时，围观党们兴高采烈地预测着 最后的排名。因为他们来自不同的班，对所有运动员不一定都了解，于是他们分别对自己了解的一些运动员的实力作出了评估，即对部分运动员做了相对排名的预 测，并且告诉了可怜留守的班长。因为无聊，于是他们就组团去打Dota去了。比赛结束后他们向班长询问最后的排名，但班长不记得了，只记得他们中哪些人的 预测是正确的，哪些人的预测是错误的。他们想知道比赛的排名可能是什么。</p>
<p>数据规模和约定<br> 1&lt; =n&lt; =10, 2&lt; =c&lt; =n, 1&lt; =m&lt; =10，保证数据合法，且答案中排名可能数不超过20000。对于一个排名序列，一个预测是正确的，当且仅当预测的排名的相对顺序 是排名序列的一个子序列。一个预测是错误的，当且仅当这个预测不正确。</p>
<h1 id="811"><a href="#811" class="headerlink" title="811"></a>811</h1><h2 id="1540-棋盘多项式"><a href="#1540-棋盘多项式" class="headerlink" title="1540: 棋盘多项式"></a><strong>1540: 棋盘多项式</strong></h2><p><a target="_blank" rel="noopener" href="https://www.dotcpp.com/oj/problem1540.html">八皇后问题的变式</a></p>
<pre><code class="lang-c++">int vis[1002][1002];
int a[10][10];
int zhong[20][20];
int nums[90];
int n ,ans =0 ,flag =0;

void fun(int l,int j,int flag )&amp;#123;        
        for (int i=j;i&gt;= 1;i--)&amp;#123;
            if(a[l][i]==0) break;
            vis[l][i] += flag ;
        &amp;#125;
        for (int i=j;i&lt;= n;i++)&amp;#123;
            if(a[l][i]==0) break;
            vis[l][i] += flag ;
        &amp;#125;
        for (int i=l;i&gt;=1;i--)&amp;#123;
            if(a[i][j]==0) break;
            vis[i][j] += flag ;
        &amp;#125;
        for (int i=l;i&lt;= n;i++)&amp;#123;
            if(a[i][j]==0) break;
            vis[i][j] += flag ;
        &amp;#125;

&amp;#125;
void dfs(int k,int x,int y,int times )&amp;#123;
    nums[times] ++ ;
    for (int i=x;i&lt;=n;i++)&amp;#123;
        for(int j=1;j&lt;=n;j++)&amp;#123;
            if(i&lt;=x&amp;&amp;j&lt;=y) continue ;
            if(vis[i][j]==0&amp;&amp;a[i][j])&amp;#123;
                fun(i,j,1);
                zhong[i][j]=1;
                dfs(k,i,j,times+1);
                zhong[i][j]=0;
                fun(i,j,-1);
            &amp;#125;
        &amp;#125; 
    &amp;#125; 
    return ;

&amp;#125;
int main()&amp;#123;   
   cin&gt;&gt; n ;
   int most =0 ;
   for (int i=1;i&lt;=n;i++)&amp;#123;
       for (int j=1;j&lt;=n;j++)&amp;#123;
           cin&gt;&gt;a[i][j];
           if(a[i][j]==1) most++ ;
       &amp;#125;
   &amp;#125;

       ans =0 ;
       memset(vis,0,sizeof(vis));
        for (int l=1;l&lt;=n;l++)&amp;#123;
            for (int j =1 ;j&lt;=n;j++)&amp;#123;
                if(vis[l][j]==0&amp;&amp;a[l][j])&amp;#123;
                    fun(l,j,1);
                    dfs(most,l,j,1);                  
                  fun(l,j,-1);
                dfs(most,l,j,0);
                flag =1 ;

               break ;
                &amp;#125; 
            &amp;#125;
            if(flag ==1 ) &amp;#123;flag =0 ;break ;&amp;#125;
        &amp;#125;
       for (int i=1;;i++)&amp;#123;
           if(nums[i]==0 ) break ;
           cout&lt;&lt;nums[i]&lt;&lt;endl;        
       &amp;#125;

&amp;#125;
</code></pre>
<p>原先额答案是：</p>
<pre><code>void dfs(int k,int x,int y,int times )&amp;#123;
    if(times &gt;= k ) &amp;#123;
        ans++;
    //    for (int i=1;i&lt;=n;i++)&amp;#123;
        //    for (int j=1;j&lt;=n;j++)&amp;#123;
            //    cout&lt;&lt;zhong[i][j]&lt;&lt;&quot; &quot;;
        //    &amp;#125;
        //    cout&lt;&lt;endl; 
    //    &amp;#125;
    //    cout&lt;&lt;endl ;
        return ;
    &amp;#125;    
    for (int i=x;i&lt;=n;i++)&amp;#123;
        for(int j=1;j&lt;=n;j++)&amp;#123;
            if(i&lt;=x&amp;&amp;j&lt;=y) continue ;
            if(vis[i][j]==0&amp;&amp;a[i][j])&amp;#123;
                fun(i,j,1);
                zhong[i][j]=1;
                dfs(k,i,j,times+1);
                zhong[i][j]=0;
                fun(i,j,-1);
                //dfs(k,i,j,times);
            &amp;#125;
        &amp;#125; 
    &amp;#125; 
    return ;

&amp;#125;
int main()&amp;#123;   
   cin&gt;&gt; n ;
   int most =0 ;
   for (int i=1;i&lt;=n;i++)&amp;#123;
       for (int j=1;j&lt;=n;j++)&amp;#123;
           cin&gt;&gt;a[i][j];
           if(a[i][j]==1) most++ ;
       &amp;#125;
   &amp;#125;

   for (int k =1 ;k&lt;=most;k++)&amp;#123;
       ans =0 ;
       memset(vis,0,sizeof(vis));
        for (int l=1;l&lt;=n;l++)&amp;#123;
            for (int j =1 ;j&lt;=n;j++)&amp;#123;
                if(vis[l][j]==0&amp;&amp;a[l][j])&amp;#123;
                    fun(l,j,1);
                //    zhong[l][j]=1;
                    dfs(k,l,j,1);

                  fun(l,j,-1);
          //        zhong[l][j]=0;
                dfs(k,l,j,0);
                flag =1 ;
                if(ans==0)&amp;#123;
                //    system(&quot;pause&quot;);
                     return 0;
                &amp;#125;
               cout &lt;&lt;ans&lt;&lt;endl;
               break ;
                &amp;#125; 
            &amp;#125;
            if(flag ==1 ) &amp;#123;flag =0 ;break ;&amp;#125;
        &amp;#125;


   &amp;#125;
  // system(&quot;pause&quot;);
&amp;#125;
</code></pre><p>时间超限，对比可以发现：</p>
<p>有些答案在dfs过程中小规模是包含在大规模里面的</p>
<p>下面学习如何处理输入的乱序数据</p>
<p>如何处理输入的10</p>
<p>如何使用vector </p>
<pre><code class="lang-c++">4 6 K Q 5 1 Q 9 7 9 K 3 J 1 2 3 5
2
3 5 7 Q 7 10 8 4 9 7 8 9 4
10 6 2 8 2 10 10 Q 5 K J 1
J 8 3 K 4 1 6 J 6

vector.front()
vector.pop_back()
vector.erase()
vector.erase(vector.begin())
vector.insert(vectoe.begin()+ x, 5) ;
</code></pre>
<pre><code class="lang-c++">#include &lt;bits/stdc++.h&gt;
using namespace std;
int f(char ch) &amp;#123;
    if (ch == &#39;K&#39;) &amp;#123;
        return 13;
    &amp;#125;
    if (ch == &#39;Q&#39;) &amp;#123;
        return 12;
    &amp;#125;
    if (ch == &#39;J&#39;) &amp;#123;
        return 11;
    &amp;#125;
    return ch - &#39;0&#39;;
&amp;#125;
int main() &amp;#123;
    vector&lt;int&gt; Puke;
    char ch;
    while (cin &gt;&gt; ch) &amp;#123;
        if (ch == &#39;0&#39;) &amp;#123; //特殊处理10
            Puke.pop_back();//将10的1出站
            Puke.push_back(10);
        &amp;#125; else &amp;#123;
            Puke.push_back(f(ch));
        &amp;#125;
    &amp;#125;
    if (Puke.size() != 52) &amp;#123;
        cout &lt;&lt; -1 &lt;&lt; endl;
        return 0;
    &amp;#125;
    vector&lt;int&gt; ans;
    while (!Puke.empty()) &amp;#123;
        int now = Puke.front();
        Puke.erase(Puke.begin());
        if (now &gt;= ans.size()) &amp;#123; //如果当前手中不足P张牌，那么就把这张牌放在最后
            ans.push_back(now);
        &amp;#125; else &amp;#123; //如果这张牌的大小是P，那么就把这张牌插入到当前手中第P张牌的后面
            ans.insert(ans.begin() + now, now);
        &amp;#125;
    &amp;#125;
    for (int i = 0; i &lt; 52; i++) &amp;#123;
        if (ans[i] == 13) &amp;#123;
            cout &lt;&lt; &#39;K&#39; &lt;&lt; &quot; &quot;;
        &amp;#125; else if (ans[i] == 12) &amp;#123;
            cout &lt;&lt; &#39;Q&#39; &lt;&lt; &quot; &quot;;
        &amp;#125; else if (ans[i] == 11) &amp;#123;
            cout &lt;&lt; &#39;J&#39; &lt;&lt; &quot; &quot;;
        &amp;#125; else &amp;#123;
            cout &lt;&lt; ans[i] &lt;&lt; &quot; &quot;;
        &amp;#125;
    &amp;#125;
    return 0;
&amp;#125;
</code></pre>
<pre><code class="lang-c++">int A[10020];
int sum[10020];
int vis[10020];
int n,m ,ans=0 ;
int maxn = -999999;
void dfs(int need ,int now ,int flag,int ans )&amp;#123;

    if(need == now  ) &amp;#123;
        if(maxn&lt;=ans) maxn = ans ;
        return ;
    &amp;#125;
    if(flag&gt;n) return ;    
    if(flag == n &amp;&amp; vis[1]==1) return ;
    if(ans+sum[flag]&gt;maxn  ) &amp;#123;
        vis[flag]=1 ;
        dfs(need,now +1 ,flag+2,ans+A[flag]);
        vis[flag]=0;
    &amp;#125; 
    if(ans+sum[flag]&gt;maxn &amp;&amp; (n-flag)/2&gt;=(need-now-1))&amp;#123;
        dfs(need,now,flag +1 ,ans);
    &amp;#125;    
&amp;#125;
int main()&amp;#123;   

   cin&gt;&gt;n&gt;&gt; m ;
   if(n/m&lt;2) &amp;#123;cout&lt;&lt;&quot;Error!&quot;&lt;&lt;endl;
   return 0 ;
   &amp;#125;
   for(int i=1;i&lt;= n;i++)&amp;#123;
       cin&gt;&gt;A[i];
   &amp;#125;
   for (int i = n ;i&gt;=1 ;i--)&amp;#123;
           if(A[i]&gt;0) ans +=A[i];
        sum[i] =ans ; 
   &amp;#125;
   dfs(m ,0, 1,0);
   cout&lt;&lt;maxn&lt;&lt;endl;

//  system(&quot;pause&quot;);
&amp;#125;
</code></pre>
<h1 id="812"><a href="#812" class="headerlink" title="812"></a>812</h1><p>大数加法</p>
<pre><code class="lang-c++">#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include&lt;string.h&gt; 
#include &lt;queue&gt;
#include &lt;cmath&gt;
#include &lt;stdlib.h&gt;
using namespace std;


int main()&amp;#123;

    string s1,s2 ;
    int answer[10020];
    cin&gt;&gt;s1&gt;&gt;s2;
    int i =s1.length()-1;
    int j =s2.length()-1 ;
    int cnt =0 ,ans=0 ;
    while(i&gt;=0&amp;&amp;j&gt;=0)&amp;#123;
        answer[++ans] = (s1[i]-48+s2[j]-48+cnt)%10;
        cnt =  (s1[i]-48+s2[j]-48+cnt)/10;
        i--;j--;
    &amp;#125;
    while(i&gt;=0)&amp;#123;
        answer[++ans] = (s1[i]-48+cnt) %10 ;
        cnt =  (s1[i]-48+cnt) /10 ;
        i--;
    &amp;#125;
    while(j&gt;=0)&amp;#123;
        answer[++ans] = (s2[j]-48+cnt) %10 ;
        cnt =  (s2[j]-48+cnt) /10 ;
        j--;
    &amp;#125;
    if(cnt&gt;0) answer[++ans] =cnt;
    for (int i=ans ;i&gt;=1;i--) cout&lt;&lt;answer[i];
    //system(&quot;pause&quot;);
&amp;#125;
</code></pre>
<p>相对问题：</p>
<p>思路：</p>
<p>①先找出No answer 的情况，就是成环，成环的判断依据：就是没有一个字母只在&gt;的前面</p>
<p>② 两两字母标注，就是将任意两个字母的关系进行联系：</p>
<p>​    <strong>方法是：dfs标记法</strong> </p>
<p><a target="_blank" rel="noopener" href="https://www.dotcpp.com/oj/problem1510.html">https://www.dotcpp.com/oj/problem1510.html</a></p>
<p>③ 最后遍历字母，如果他出现在排列队伍中，则将他加入队伍answer中，加入那个位置：</p>
<p>​    就是从前到后遍历队伍，插入到比下一个数大的前面</p>
<p>   若没有这种情况则插入队尾</p>
<pre><code class="lang-c++">int a[1002][1002];
int have[133],di[133],yu[133];
vector&lt;char&gt; vec[133];
vector&lt;char&gt; answer;
void dfs(int k,int now)&amp;#123;    //可优化
    for(int i=0;i&lt;vec[now].size();i++)&amp;#123;
        a[k][vec[now][i]] =1 ;
        a[vec[now][i]][k] =-1 ;
        dfs(k,vec[now][i]);
    &amp;#125;
&amp;#125;
int main()&amp;#123;   
   string s ;
   char ch ;
   int num =0 ;

   while (cin&gt;&gt;s&amp;&amp;)&amp;#123;
         a[s[0]][s[2]] = 1 ;
         a[s[2]][s[0]] = -1;
         vec[s[0]].push_back(s[2]);
         have[s[0]]=1;
         have[s[2]]=1;
         if(yu[s[0]]==0) num++,yu[s[0]]=1;
         if(yu[s[2]]==0) num++,yu[s[2]]=1;
         di[s[2]] =1 ;

   &amp;#125; 
   //不可能的情况 

   for (int i=65;i&lt;=90;i++)&amp;#123;
       if(have[i]&amp;&amp;!di[i]) &amp;#123;
           ch = i ;
           break ;
       &amp;#125;
       if(i==90) &amp;#123;
           cout&lt;&lt;&quot;No  Answer!&quot;&lt;&lt;endl;
           return 0;
       &amp;#125;
   &amp;#125;
   //标记祖辈 
   for (int i=65;i&lt;=90;i++)&amp;#123;
           for(int j =0 ;j&lt;vec[i].size();i++)&amp;#123;
               dfs(i,vec[i][j]);         
       &amp;#125;
   &amp;#125;



       answer.push_back(ch);
       for (int i=65;i&lt;=90;i++)&amp;#123;
           int t =0 ;
           char k = i ;
           if(k==answer[0]) continue ;
           if(have[i]==1)&amp;#123;
               for (int j = 0 ; j&lt;answer.size();j++ )&amp;#123;
                   if(a[i][answer[j]]==1) &amp;#123;
                       t=1,answer.insert(answer.begin()+j,i);
                       break ;
                   &amp;#125;
               &amp;#125;
               if(t==0) answer.push_back(i);
           &amp;#125;
       &amp;#125;
       for (int i=0;i&lt;answer.size();i++) cout&lt;&lt;answer[i];


  //system(&quot;pause&quot;);
&amp;#125;
</code></pre>
<h1 id="813"><a href="#813" class="headerlink" title="813"></a>813</h1><p>:100: 到底是贪心算法还是背包问题？？？</p>
<p><strong>贪吃的大嘴</strong><a target="_blank" rel="noopener" href="https://www.dotcpp.com/oj/problem1566.html">https://www.dotcpp.com/oj/problem1566.html</a></p>
<p>多重背包问题，贪心算法</p>
<h2 id="邮票面值设计"><a href="#邮票面值设计" class="headerlink" title="邮票面值设计"></a><strong>邮票面值设计</strong></h2><p><a target="_blank" rel="noopener" href="https://www.dotcpp.com/oj/problem1576.html是一道好题目，dfs+dp">https://www.dotcpp.com/oj/problem1576.html是一道好题目，dfs+dp</a></p>
<pre><code class="lang-c++">//so easy
#include&lt;iostream&gt;
#include&lt;cstring&gt;//头文件
using namespace std;
int a[17],n,k,ans[17],maxn;//a【】表示这种方法的邮票，ans【】表示如今取得的解即要输出的
int dp(int t,int mx)&amp;#123;    
    int f[50000];//f[i]为拼i所需的最少数的个数
    f[0]=0;//边界
    for(int i=1;i&lt;=a[t]*n;i++)
      f[i]=50000;//赋初值赋一个尽可能地大就可以了
    for(int i=1;i&lt;=t;i++)            //从第一位找到目前的位数把所有已找的邮票都枚举 
      for(int j=a[i];j&lt;=a[t]*n;j++)   //因为不可能找到比自己小的数，所以从自己开始找 
        f[j]=min(f[j],f[j-a[i]]+1);    //比较上几次已找到的最小需要位数和即将要找的相比较，取较小值
    for(int i=1;i&lt;=a[t]*n;i++)      
        if(f[i]&gt;n)  return i-1;   //如果所需最小的个数大于n就意味着这种情况不符合，但f【i-1】是符合的不然f【i-1】就会判断所以不符合返回i-1

     return a[t]*n;//如果到a【t】*n的f【i】都满足意味着能取到的最大连续数就是a【t】*n&amp;#125;

void dfs(int t,int mx)&amp;#123;              // 为什么全部找完：因为多几张邮票肯定比少几张邮票可能的情况多，所以全部找完是最好的  
    if(t==k+1)&amp;#123;        //如果所有邮票数已经找完，那么就和 maxn比较谁更大   
        if(mx&gt;maxn)&amp;#123;
            maxn=mx;            
          for(int i=1;i&lt;=t-1;i++)
              ans[i]=a[i];&amp;#125; //保存所需要的邮票面值  
        return;
        &amp;#125;   
    for(int i=a[t-1]+1;i&lt;=mx+1;i++)&amp;#123;  
        //继续找：为了避免重复，下一张邮票要比上一张邮票大，所以上边界是a[t-1]+1，同时它不能比最大连续值+1还大，不然最大连续值的下一个数就永远连不起来了 
      a[t]=i;      
       int x=dp(t,mx);   //t张动归寻找此时的最大连续数 
      dfs(t+1,x);
    &amp;#125;
&amp;#125;
int main()&amp;#123;    
    cin&gt;&gt;n&gt;&gt;k;
    dfs(1,0);  //先从第一张开始找，第一张前面没有数，所以所连续的最大数为 0 
    for(int i=1;i&lt;=k;i++)//输出 注意打空格以及大写换行即可
      cout&lt;&lt;ans[i]&lt;&lt;&quot; &quot;;    cout&lt;&lt;endl;    cout&lt;&lt;&quot;MAX=&quot;&lt;&lt;maxn&lt;&lt;endl;    return 0;
&amp;#125;
</code></pre>
<p>dp表示用最少的钱的数目表示尽可能大的数</p>
<p>一种处理坐标轴模拟计算的方法：</p>
<pre><code>#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include&lt;string.h&gt; 
#include &lt;queue&gt;
#include &lt;cmath&gt;
#include &lt;stdlib.h&gt;
using namespace std;
bool vis[1000020];
bool T[1000020];
vector&lt;int&gt;zhi;
 int a[10010][5]; 
int main()&amp;#123;   
int n ;
  cin&gt;&gt;n ;
  for(int i=1;i&lt;=n;i++)&amp;#123;
      for(int j =1 ;j&lt;=4;j++)&amp;#123;
          cin&gt;&gt;a[i][j];
      &amp;#125;
  &amp;#125;
  int x,y;
  cin&gt;&gt;x&gt;&gt;y ;
  for (int i=n;i&gt;=1;i--)&amp;#123;
      if(x&gt;=a[i][1]&amp;&amp;x&lt;=a[i][1]+a[i][3]&amp;&amp;y&gt;=a[i][2]&amp;&amp;y&lt;=a[i][2]+a[i][4]) &amp;#123;
          cout&lt;&lt;i;
          //system(&quot;pause&quot;);
          return 0 ;
      &amp;#125;
  &amp;#125;
  cout&lt;&lt;-1;
&amp;#125;
</code></pre><p>815</p>
<pre><code class="lang-c++">#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include&lt;string.h&gt; 
#include &lt;queue&gt;
#include &lt;cmath&gt;
#include &lt;stdlib.h&gt;
using namespace std;
string s[200];
vector&lt;int&gt; vec[200];
int vis[200];
int lenij[22][22];//后面j不重叠的长度 
int maxn = 0 ;
vector&lt;int&gt;answer;
int  fun(int k1,int k2 )&amp;#123;
    string s1 =s[k1],s2 =s[k2];
    int k = -1 ;
    for(int i=s1.length();i&gt;=0;i--) &amp;#123;
        if(s1[i]==s2[0]) &amp;#123;
            int j =0 ;
            int k = i ;
            int flag =0 ;
            if(s1.length()-k &gt; s2.length()) continue ;//esdse sds 
            while(k&lt;=s1.length()-1 &amp;&amp;j&lt;=s2.length()-1)&amp;#123;
                if(s1[k]==s2[j]) &amp;#123;k++,j++;&amp;#125;
                else &amp;#123;flag =1 ;break ;&amp;#125; 
            &amp;#125;
        //    cout &lt;&lt; k1&lt;&lt;k2&lt;&lt;i&lt;&lt;j&lt;&lt;k&lt;&lt;&quot; &quot;;

            if(k == s1.length()&amp;&amp;s1.length()-i == j)&amp;#123;
        //        cout &lt;&lt; &quot;ok&quot;;
                if(i==0) &amp;#123;
                    if(s1.length()!=s2.length()) return 0;
                    else continue ;
                &amp;#125;
                else if(j==s2.length()) return 0 ;
                else if(j&lt;=s2.length()-1)&amp;#123;
                    lenij[k1][k2] =s2.length()-j ; return 1 ;
                &amp;#125; 
            &amp;#125;

        &amp;#125;
    &amp;#125;

    return 0;
&amp;#125;
void dfs(int k,int len )&amp;#123;

    if(len&gt;maxn)&amp;#123;
        maxn = len ;
    //    for (int i=0;i&lt;answer.size();i++) cout&lt;&lt;answer[i];
    //    cout&lt;&lt;&quot; &quot;&lt;&lt;len&lt;&lt;endl;


    &amp;#125;

//    cout&lt;&lt;k&lt;&lt;len&lt;&lt;endl ;
    for (int i=0;i&lt;vec[k].size();i++)&amp;#123;
        int j = vec[k][i];
        if(vis[j]&lt;2) &amp;#123;
            if(lenij[k][j]&gt;0)&amp;#123;
                answer.push_back(j);
                vis[j]++;
                dfs(j,len+lenij[k][j]);
                vis[j]--;
                answer.pop_back();
            &amp;#125;
        &amp;#125; 
    &amp;#125;
//    cout&lt;&lt;-1&lt;&lt;endl ;
    return ;
&amp;#125;
int main()&amp;#123;
    int n ;
     cin&gt;&gt; n ;
     memset(lenij,0,sizeof(lenij));
     for (int i=1;i&lt;=n;i++)&amp;#123;
         cin&gt;&gt;s[i];
     &amp;#125; 
     for (int i=1;i&lt;= n;i++)&amp;#123;
         for (int j=1;j&lt;=n;j++)&amp;#123;
             if(fun(i,j)) vec[i].push_back(j);
         &amp;#125;
    //     cout&lt;&lt;endl ;
     &amp;#125;
     for (int i=1;i&lt;=n;i++)&amp;#123;
         for (int j=1;j&lt;=n;j++)&amp;#123;
         //    cout&lt;&lt;lenij[i][j]&lt;&lt;&quot; &quot;;
         &amp;#125;
    //     cout&lt;&lt;endl ;
     &amp;#125;
     char ch ;
     cin&gt;&gt;ch ;
     for (int i=1;i&lt;=n;i++)&amp;#123;
         if(s[i][0]==ch)&amp;#123;
                 vis[i]++;
         answer.push_back(i);
         dfs(i,s[i].length());
         answer.pop_back();
         vis[i]--;
         &amp;#125;

     &amp;#125;
     cout&lt;&lt;maxn ;

    //system(&quot;pause&quot;);
&amp;#125;
</code></pre>
<p>913数的划分</p>
<p>范围比较小的时候可以选择暴力并保存。</p>
<pre><code class="lang-c++">#include &lt;stdio.h&gt;
int f[102];
int main() &amp;#123;
    int n;
    scanf(&quot;%d&quot;,&amp;n);
    f[0] = 1;
    for(int i = 1; i &lt;= n; i++)
        for(int j = i; j &lt;= n; j++)
            f[j] = f[j] + f[j-i];
    printf(&quot;%d\n&quot;,f[n]);
    return 0;
&amp;#125;
</code></pre>
<pre><code class="lang-c++">bool cmp(string sx,string sy)&amp;#123;

    for (int i=6;i&lt;=13;i++)&amp;#123;
        if(sx[i]!=sy[i]) return sx[i]&gt;sy[i]; 
        else continue ;
    &amp;#125;
    return sx&gt;sy;
&amp;#125;
int main()&amp;#123;
    int n ;
    cin &gt;&gt;n ;
    for (int i=1;i&lt;=n;i++)&amp;#123;
        cin&gt;&gt;s[i];
    &amp;#125;
    sort(s+1,s+1+n,cmp);
    for(int i=1;i&lt;=n;i++)&amp;#123;
        cout&lt;&lt; s[i]&lt;&lt;endl ;
    &amp;#125;
//    system(&quot;pause &quot;);
&amp;#125;

//对比：
#include&lt;bits/stdc++.h&gt; /* 525 ms 使用 string */  
using namespace std;
const int len = 100010;

struct person &amp;#123;
    string num;
    string bro;
&amp;#125; datas[len];

int cmp(person perst, person pernd) &amp;#123;
    if (perst.bro == pernd.bro)
        return perst.num &gt; pernd.num;
    else
        return perst.bro &gt; pernd.bro;
&amp;#125;

int main() &amp;#123;
    int num; cin &gt;&gt; num;
    for (int i = 0; i &lt; num; i++) &amp;#123;
        datas[i].num.resize(19);
        scanf(&quot;%s&quot;, &amp;datas[i].num[0]);
        datas[i].bro = datas[i].num.substr(6, 8);
        //substr从第六个字母开始长度为8 的字符串。
    &amp;#125;

    sort(datas, datas + num, cmp);
    for (int i = 0; i &lt; num; i++)
        puts(datas[i].num.c_str());
</code></pre>
<pre><code class="lang-c++">#include&lt;bits/stdc++.h&gt;
using namespace std;

int Len;
bool Vis[31309];
typedef struct &amp;#123;
    string Pass; int Step;
&amp;#125; status;
queue&lt;status&gt; que;

bool find(string Pass) &amp;#123;
    if (Pass.find(&quot;2012&quot;) == string::npos) //是否存在，==是不存在子串
        //string::npos,steing ::npos,string::npos;
        return false;
    return true;
&amp;#125;

int Hash(string Pass) &amp;#123;
    int hash = 0;
    for (int i = 0; i &lt; Len; i++)
        hash += hash * 2 + Pass[i] - 41;
    return hash % 29231;
&amp;#125;

int BFS() &amp;#123;
    while (!que.empty()) &amp;#123;
        status now = que.front(); que.pop();//front---pop---push

        for (int pos = 0; pos &lt; Len - 1; pos++) &amp;#123;
            swap(now.Pass[pos], now.Pass[pos + 1]); 
            now.Step++;

            if (find(now.Pass))
                return now.Step;
            int hashValue = Hash(now.Pass);
            if (!Vis[hashValue]) &amp;#123;
                Vis[hashValue] = true; que.push(now);
            &amp;#125;
            now.Step--;
            swap(now.Pass[pos], now.Pass[pos + 1]);
        &amp;#125;
    &amp;#125;
    return -1;
&amp;#125;

int main() &amp;#123;
    status start; start.Step = 0;
    cin &gt;&gt; Len &gt;&gt; start.Pass;
    if (start.Pass.find(&quot;2012&quot;) == string::npos) &amp;#123;
        que.push(start); cout &lt;&lt; BFS();
    &amp;#125;
    else cout &lt;&lt; 0;
&amp;#125;
</code></pre>

      
       <hr><span style="font-style: italic;color: gray;"> 转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2572876783@qq.com </span>
    </div>
</article>


<p>
    <a  class="dashang" onclick="dashangToggle()">💰</a>
</p>






    
        <!-- MathJax配置，可通过单美元符号书写行内公式等 -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
    "HTML-CSS": {
        preferredFont: "TeX",
        availableFonts: ["STIX","TeX"],
        linebreaks: { automatic:true },
        EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)
    },
    tex2jax: {
        inlineMath: [ ["$", "$"], ["\\(","\\)"] ],
        processEscapes: true,
        ignoreClass: "tex2jax_ignore|dno",
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
        equationNumbers: { autoNumber: "AMS" },
        noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" } },
        Macros: { href: "{}" }
    },
    messageStyle: "none"
    });
</script>
<!-- 给MathJax元素添加has-jax class -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for(i=0; i < all.length; i += 1) {
            all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>
<!-- 通过连接CDN加载MathJax的js代码 -->
<script type="text/javascript" async
        src="//cdn.jsdelivr.net/npm/mathjax@2.7.8/unpacked/MathJax.js?config=TeX-MML-AM_CHTML">
</script>
<input type="hidden" id="MathJax-js"
        value="//cdn.jsdelivr.net/npm/mathjax@2.7.8/unpacked/MathJax.js?config=TeX-MML-AM_CHTML">
</input>
    




    </div>
    <div class="copyright">
        <p class="footer-entry">
    ©2016-2020 MOLU
</p>
<p class="footer-entry">Built with <a href="https://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/yelog/hexo-theme-3-hexo" target="_blank">3-hexo</a> theme</p>

    </div>
    <div class="full-toc">
        <button class="full" data-title="切换全屏 快捷键 s"><span class="min "></span></button>
<a class="" id="rocket" ></a>

    </div>
</div>

<div class="hide_box" onclick="dashangToggle()"></div>
<div class="shang_box">
    <a class="shang_close"  onclick="dashangToggle()">×</a>
    <div class="shang_tit">
        <p>Help us with donation</p>
    </div>
    <div class="shang_payimg">
        <div class="pay_img">
            <img src="/img/alipay.jpg" class="alipay" title="扫码支持">
            <img src="/img/weixin.jpg" class="weixin" title="扫码支持">
        </div>
    </div>
    <div class="shang_payselect">
        <span><label><input type="radio" name="pay" checked value="alipay">alipay</label></span><span><label><input type="radio" name="pay" value="weixin">weixin</label></span>
    </div>
</div>


</body>
<script src="/js/jquery.pjax.js?v=1.1.0" ></script>

<script src="/js/script.js?v=1.1.0" ></script>
<script>
    var img_resize = 'default';
    function initArticle() {
        /*渲染对应的表格样式*/
        
            $("#post .pjax table").addClass("green_title");
        

        /*渲染打赏样式*/
        
        $("input[name=pay]").on("click", function () {
            if($("input[name=pay]:checked").val()=="weixin"){
                $(".shang_box .shang_payimg .pay_img").addClass("weixin_img");
            } else {
                $(".shang_box .shang_payimg .pay_img").removeClass("weixin_img");
            }
        })
        

        /*高亮代码块行号*/
        

        /*访问数量*/
        
        $.getScript("//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js");
        

        /*代码高亮，行号对齐*/
        $('.pre-numbering').css('line-height',$('.has-numbering').css('line-height'));

        
        
    }

    /*打赏页面隐藏与展示*/
    
    function dashangToggle() {
        $(".shang_box").fadeToggle();
        $(".hide_box").fadeToggle();
    }
    

</script>

<!--加入行号的高亮代码块样式-->

<!--自定义样式设置-->
<style>
    
    
    .nav {
        width: 542px;
    }
    .nav.fullscreen {
        margin-left: -542px;
    }
    .nav-left {
        width: 120px;
    }
    
    
    @media screen and (max-width: 1468px) {
        .nav {
            width: 492px;
        }
        .nav.fullscreen {
            margin-left: -492px;
        }
        .nav-left {
            width: 100px;
        }
    }
    
    
    @media screen and (max-width: 1024px) {
        .nav {
            width: 492px;
            margin-left: -492px
        }
        .nav.fullscreen {
            margin-left: 0;
        }
    }
    
    @media screen and (max-width: 426px) {
        .nav {
            width: 100%;
        }
        .nav-left {
            width: 100%;
        }
    }
    
    
    .nav-right .title-list nav a .post-title, .nav-right .title-list #local-search-result a .post-title {
        color: #383636;
    }
    
    
    .nav-right .title-list nav a .post-date, .nav-right .title-list #local-search-result a .post-date {
        color: #5e5e5f;
    }
    
    
    .nav-right nav a.hover, #local-search-result a.hover{
        background-color: #e2e0e0;
    }
    
    

    /*列表样式*/
    

    /* 背景图样式 */
    
    


    /*引用块样式*/
    

    /*文章列表背景图*/
    

    
</style>







</html>
